﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
    class P0005: IProblem
    {
        public void Run()
        {
            var list = new List<string>
            {
                //"babad",
                //"154",
                //"cbbd",
                //"qgjjgqwvvvw",
                "aaaa",
                //"rgczcpratwyqxaszbuwwcadruayhasynuxnakpmsyhxzlnxmdtsqqlmwnbxvmgvllafrpmlfuqpbhjddmhmbcgmlyeypkfpreddyencsdmgxysctpubvgeedhurvizgqxclhpfrvxggrowaynrtuwvvvwnqlowdihtrdzjffrgoeqivnprdnpvfjuhycpfydjcpfcnkpyujljiesmuxhtizzvwhvpqylvcirwqsmpptyhcqybstsfgjadicwzycswwmpluvzqdvnhkcofptqrzgjqtbvbdxylrylinspncrkxclykccbwridpqckstxdjawvziucrswpsfmisqiozworibeycuarcidbljslwbalcemgymnsxfziattdylrulwrybzztoxhevsdnvvljfzzrgcmagshucoalfiuapgzpqgjjgqsmcvtdsvehewrvtkeqwgmatqdpwlayjcxcavjmgpdyklrjcqvxjqbjucfubgmgpkfdxznkhcejscymuildfnuxwmuklntnyycdcscioimenaeohgpbcpogyifcsatfxeslstkjclauqmywacizyapxlgtcchlxkvygzeucwalhvhbwkvbceqajstxzzppcxoanhyfkgwaelsfdeeviqogjpresnoacegfeejyychabkhszcokdxpaqrprwfdahjqkfptwpeykgumyemgkccynxuvbdpjlrbgqtcqulxodurugofuwzudnhgxdrbbxtrvdnlodyhsifvyspejenpdckevzqrexplpcqtwtxlimfrsjumiygqeemhihcxyngsemcolrnlyhqlbqbcestadoxtrdvcgucntjnfavylip",
            };
            foreach (var str in list)
            {
                var result = longestPalindrome(str);
                Console.WriteLine(string.Format("input:{0} output:{1}", str, result));
            }

            foreach (var str in list)
            {
                var result = longestPalindromeOutofTime(str);
                Console.WriteLine(string.Format("input:{0} output:{1}", str, result));
            }
        }
        public string longestPalindrome(string s)
        {
            if (string.IsNullOrEmpty(s))
                return s;
            string result = null;
            var arr = s;
            int maxLength = 0;
            int maxStart = 0;
            int maxEnd = 0;

            for (int i = 0; i < arr.Length; i++)
            {
                if (i + 1 < arr.Length && arr[i] == arr[i + 1])
                {
                    //偶数个可能.
                    for (int j = 0; i - j >= 0 && i + j + 1 < arr.Length; j++)
                    {
                        if (arr[i + j + 1] == arr[i - j])
                        {
                            if (j + j + 1 > maxLength)
                            {
                                maxStart = i - j;
                                maxEnd = i + j + 1;
                                maxLength = j + j + 1;
                            }
                            continue;
                        }

                        break;
                    }
                }
                //奇数个可能.
                for (int j = 0; i - j >= 0 && i + j < arr.Length; j++)
                {
                    if (arr[i + j] == arr[i - j])
                    {
                        if (j + j > maxLength)
                        {
                            maxStart = i - j;
                            maxEnd = i + j;
                            maxLength = j + j;
                        }
                        continue;
                    }

                    break;
                }

            }
            result = s.Substring(maxStart, maxEnd - maxStart + 1);
            return result;
        }

        public string longestPalindromeOutofTime(string s)
        {
            if (string.IsNullOrEmpty(s))
                return s;
            string result = null;
            var arr = s.ToCharArray();
            int startIndex = 0;
            int maxStart = 0, maxEnd = 0;


            while (startIndex < arr.Length)
            {
                int endIndex = arr.Length - 1;
                while (endIndex > startIndex)
                {
                    int curIndex = startIndex;
                    bool isPalindromic = true;
                    while (curIndex <= (endIndex + startIndex) / 2)
                    {
                        isPalindromic &= arr[curIndex] == arr[endIndex - (curIndex - startIndex)];
                        curIndex++;
                    }
                    if (isPalindromic)
                    {
                        if (endIndex - startIndex > maxEnd - maxStart)
                        {
                            maxEnd = endIndex;
                            maxStart = startIndex;
                            //Console.WriteLine(string.Format("endIndex:{0} startIndex:{1}", endIndex, startIndex));

                        }
                        break;
                    }
                    endIndex--;
                }
                startIndex++;
            }

            result = s.Substring(maxStart, maxEnd - maxStart + 1);
            return result;
        }
    }
}
